package org.basis.algorithm.bitoperation;

import org.basis.algorithm.common.BitOperationUtil;

/**
 * 查找出现奇数次数的一个数字
 *
 * @author Mr_wenpan@163.com 2021/12/02 16:04
 */
public class FindOddNumber {

    public static void main(String[] args) {
        int[] arr = {22, 33, 33, 33, 22, 11, 11, 10, 10};
        System.out.println("eor = " + process(arr));
        //提取最右侧的1
        System.out.println("BitOperationUtil.extractRightOne(9) = " + BitOperationUtil.extractRightOne(12));

        int[] array = {22, 33, 33, 33, 22, 11, 11, 10, 10, 1, 1, 1};
        process1(array);
    }

    /**
     * 一个数组中只有一种数字出现了奇数次，请找出这个数字
     */
    private static int process(int[] arr) {
        if (arr == null) {
            return -1;
        }
        if (arr.length < 2) {
            return arr[0];
        }
        int eor = 0;
        for (int value : arr) {
            eor = eor ^ value;
        }
        return eor;
    }

    /**
     * 一个数组中有2种数字出现了奇数次，请找出这2种数字
     * 假设这两种数字为a和b
     */
    private static void process1(int[] arr) {

        int eor = 0;
        for (int value : arr) {
            eor = eor ^ value;
        }

        // 此时eor就相当于a^b了，重要的是如何将a和b区分出来
        // 因为a != b，所以 a^b != 0，那么说明a^b的至少某一位上等于1，那么是哪一位呢？暂且定位x位置
        // 此时就可以把数组中的数分为两类，一类是x位为1的数，一类是x位为0的数，如果使用rightOne去与所有x位为1的数，那么得到的就是a或b
        int rightOne = BitOperationUtil.extractRightOne(eor);
        int a = 0;
        for (int value : arr) {
            // 找到x位置为0的数
            int temp = rightOne & value;
            if (temp == 0) {
                a = a ^ value;
            }
        }
        int b = a ^ eor;
        System.out.println("第一个数是：" + a);
        System.out.println("第二个数是：" + b);
    }
}
